A typical IP network employs a plurality of routers, connected by links, to route data packets representing information (e.g., a telephone call using VoIP (voice over Internet Protocol)) independently from an origin to a destination based on a destination address in each packet. IP networks of the type described above are characterized by best effort routing, and an example of routing that is prevalent is the Open Shortest Path First (OSPF) protocol. Other routing protocols are often derived from OSPF routing. For example, LSPs (Label Switched Paths) are created using the MPLS (Multi Protocol Label Switching) protocol on the routes derived from the OSPF protocol, and an IP packet is transmitted by attaching one or more MPLS labels, corresponding to the respective LSP, to the IP packet. Thus in referring to OSPF protocols in this application, we mean to embrace other named protocols that build on OSPF routing solutions.
In the OSPF protocol, routers within the network exchange information with each other by a flooding technique so that each router maintains a database of the network topology. Using the information in its stored database, each router selects a path to all other routers in accordance with user-established cost metrics that typically require the shortest possible path. Data packets are forwarded based on the destination IP address in the packet along the path selected to the router that can reach the destination IP address either directly or via another network or sub-network. When multiple choices are available, the path with the minimum cost metric is selected. Using such cost metrics, each router establishes its routing table accordingly so each router can select a path having, for example, a minimum number of links.
It is desirable with any routing scheme to avoid packet loss, which requires information to be resent and places added demands on network capacity. As explained below, OSPF routing is vulnerable to packet loss in certain situations.
A normally configured OSPF network has a two-level hierarchy partitioned into multiple areas. “Area zero” is always assigned to the core OSPF network and defines the higher level of the hierarchy. Area IDs >0 are assigned to all other areas and they belong to the lower level of the hierarchy. These areas are referred to as “area ones”. Area zero must be contiguous and all area ones must attach to area zero. The OSPF hierarchy and areas are used to limit the flooding of OSPF Link State Advertisement (LSA) messages (messages are flooded only to nodes in the same area) as well as to constrain how routes are calculated and how traffic flows between two nodes (traffic between routers in an area must stay on links in that area, e.g., area zero traffic cannot dip down into area ones). Within an area, routes are calculated using the Dijkstra shortest path algorithm, which calculates the shortest routes from a source node to all other (destination) nodes in one pass of the algorithm. Shortest path routing is required for all traffic within an area, even if it exceeds link capacities resulting in packet drops (accordingly, it is the responsibility of network administrators to see that links have adequate capacity). Traffic can pass between areas only through an area border router (ABR), a router with links in more than one area. The ABR summarizes reachability information (sets of reachable IP addresses and costs) in an area and sends it to other areas.
The Dijkstra algorithm is used within each area and operates on an administrative weight parameter assigned to each link in that area. In reality, each link is a bidirectional link with an administrative weight parameter associated with each direction. For simplicity, we ignore this distinction as the two weights are almost always identical.
A large IP network could have hundreds or even thousands of routers. Typically, users connect to such a network through lots of small “edge routers”, where small is a relative term and refers to the amount and size of packets the device is capable of transmitting. Larger customers, such as big enterprises, typically connect to the IP network through large edge routers. Often, many small edge routers in a region may be aggregated through a large edge router in the same region. Other routers, called hub or aggregation routers are used to further aggregate traffic from edge routers in a region. The hub routers then feed the aggregated traffic to a small number of core routers. The core routers are the biggest routers in the network and are typically situated in most major cities. They are connected to each other using a mesh topology. The IP network thus appears like a hierarchy of routers. At the top of the hierarchy is a flat level of core routers in a meshed topology. In each geographic region, there is a vertical stack of routers with the smallest edge routers at the bottom and the hub routers at the top of the stack connecting into one or a few core routers in that region.
The core routers are all part of OSPF area zero. The core routers are typically very large routers with multiple high-speed OC192 and OC768 links between them. The edge routers in a region are all grouped into an OSPF “area one” with a unique area id greater than zero. Often, the edge routers are further segregated by service into different area ones. The connectivity within an area one is generally like a vertical tree. Small edge routers connect to one or two large edge routers. Large edge routers connect to one or two hub routers and, in turn, hub routers connect to two core routers. Traffic from one large edge router to another large edge router does not flow on a direct link and instead must pass through a hub router or a core router or both routers. In OSPF, paths are chosen without explicitly taking the sizes of links into account. Hence, if routers of different sizes are placed in a flat topology, then a path may include links (out of the smaller routers) with insufficient bandwidth to handle the IP traffic on this path, resulting in packet drops.
The hub router need not be as large as a core router and has smaller size (up)links to the core as compared to the links within the core, with just one or two pairs of OC192 or 10 GigE uplinks in many cases. The hub router uplinks to the core can be included in OSPF area zero. It would be desirable to include hub routers in area zero, by designating some of their links to be area zero links, because area definitions would be simplified and it would be much easier to provision network links. However, there is a drawback when hub routers are included in area zero, which is that in certain conditions core traffic may be routed through the hubs and their area zero links.
In a normally configured OSPF network, links can be weighted to influence routing choices. The administrative weight of the hub uplinks to the core can be set high enough to discourage any traffic between two core routers from taking a route passing through the hub routers. This is a simple and usually preferred option. However, it suffers from one potential problem that makes network architects uneasy. There could be conditions, particularly under multiple failures and/or maintenance downtime scenarios, when core traffic is routed through these smaller size uplinks, overwhelming their capacity and resulting in a very large number of packet drops. Even if the network topology provides multiple paths for core traffic, one or more failures in the network could create a situation when many or all other alternate paths are unavailable. Because of this possibility, hub routers are not put in area zero.
The advent of new services and network configurations increases the difficulty of maintaining OSPF area zero traffic integrity. A service provider like AT&T offers many IP services such as Internet Access and different flavors of Virtual Private Network (VPN) service over separate edge routers. Edge routers are assigned to different OSPF areas according to the particular IP service they provide in a site. This creates a complicated situation where the core and hub routers have to be part of several OSPF areas. This situation is much more difficult to manage and is prone to router provisioning errors. This situation only becomes more complex in configurations where hub routers are dual-homed, e.g., to two core routers in two different locations.
One approach taken by the prior art to solve such problems is to engraft additional levels into the OSPF protocol, for example, to employ a three level approach. One drawback to these efforts is that they change OSPF procedures to such a large degree that they are tantamount to developing a brand new routing protocol. For example, the PNNI (Private Network to Network Interface) with a multi-level hierarchy was developed for ATM (Asynchronous Transfer Mode) networks. Even though PNNI has many OSPF-like features, it is a completely different protocol.
Most of the prior art and, in particular, the work done in the ASON (Automatically Switched Optical Network) and OIF (Optical Internetworking Forum) groups deals with the creation of a multi-level hierarchy spanning multiple networks or domains (within a network). The main intent of such solutions is to allow the networks to scale. The effort is directed towards creating a less detailed view as one goes up the hierarchy with lower levels offering summarized topology and reachable address information to higher levels. As an example, if many networks are connected to each other at interconnection points (over E-NNI links), then the highest level of the hierarchy could represent each network as a “node” with links between these “nodes” representing the E-NNI links. Routes in higher levels of the hierarchy are no longer “real” routes. At the highest level of the hierarchy, such a “logical” route may just specify the networks that are transited.
When a hierarchy is created and topology abstraction is used, the advertised topology can be a transformed view of the actual internal topology of a domain. There is no view of the actual internal topology of contained “Routing Areas” (synonymous to an OSPF area) and this may significantly affect routing performance.
All these prior art efforts effectively require a fork lift overhaul of the network protocols (i.e., a complete changeover with attendant hardware and software consequences) and as a consequence have never been used to upgrade existing networks.
Accordingly, there is a need to provide a method for accommodating routers of different sizes in a flat OSPF topology and routing traffic in an OSPF network so that, in breakdown situations, packets associated with area zero traffic will not be dropped. There is a further need to provide an OSPF network that is capable of operating in breakdown situations while avoiding dropping packets associated with area zero traffic. There is a further need to be able to upgrade existing OSPF-based networks to achieve such results without major turmoil, and preferably with only a new software release.